/* Quick sort: partition an array on an element (pivot) such that all elements
 * to the left are smaller and all the elements to the right are greater.
 * Recursively quick sort the two sub arrays, not including the pivot element
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *x, int *y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}


void print_arr(int arr[], int n)
{
	int i = 0;

	for (i = 0; i < n; i++)
		printf("%4d ", arr[i]);

	printf("\n");
}


/* Returns a pivot index such that all elements to the left are smaller and all
 * elements to the right are greater than that element */
int partition(int arr[], int n)
{
	int rand_pos = rand()%n;
	int pivot_val;
	int pivot_index = 0;
	int i =0;

	if ( n <= 1)
		return n;

	swap(&arr[rand_pos], &arr[n-1]);
	pivot_val = arr[n-1];

	for (i=0; i < n-1; i++) {
		if(arr[i] < pivot_val)
			swap(&arr[i], &arr[pivot_index++]);
	}

	swap(&arr[pivot_index], &arr[n-1]);

	return pivot_index;
}


void quick_sort(int arr[], int n)
{
	int pivot_index = 0;

	if (n <= 1)
		return;

	pivot_index = partition(arr, n);

	if (pivot_index > 0)
		quick_sort(arr, pivot_index);

	if (pivot_index < n-1)
		quick_sort(arr+pivot_index+1, n-pivot_index-1);
}


int main(void)
{
	int arr[] = { 99, 22, 13, 43, 67, 7, 27, 23, 4, 15, 81, 46, 64, 8, 17, 18, 19 };
	int size = sizeof(arr) / sizeof(arr[0]);
	srand(time(NULL));

	print_arr(arr, size);
	quick_sort(arr, size);
	print_arr(arr, size);

	return 0;
}
